#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 122. 买卖股票的最佳时机 II.py
@time: 2022/3/3 21:53
@desc: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
> 给定一个数组 prices ，其中prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候最多只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润。

1. DP
2.  当前dp可能是持有或者不持有，最后一天的dp一定是不持有的，转移方程：
        dp0[i] = max(dp0[i-1], dp0[i]+price[i])
        dp1[i] = max(dp1[i-1], dp0[i]-price[i])
'''

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp0, dp1 = 0, -prices[0]
        for i in range(1, n):
            # 第i天不持有股票，从前一天不持股和前一天持股中的最大值在当天卖出中选出
            newD0 = max(dp0, dp1+prices[i])
            # 第i天持有股票，从前一天持股和今天买入股票的最大值中选出
            newD1 = max(dp1, dp0-prices[i])
            dp0, dp1 = newD0, newD1
        # 最后一天必不买入
        return dp0